Space-time constraints
$$ \def\F{\mathbb F} $$
Goal. Simulate a form of (random access) memory using bivariate polynomials $P\in\F[X,Y]$.
Intuitively, we lay out the memory with time on the $X$ axis and space (addresses) on the $Y$ axis.
Stack
Start with a simple stack where $P(𝜔_n^i, 𝜔_m^j)$ is the value of stack location $j$ at time $i$.
The initial polynomial is the zero polynomial on our basis $𝜔^j$
$$ P(0, Y) = Y^m - 1 $$
Note. It looks like we can handle the memory sparsely, both in the polyonmial form and in the merkle trees.
$$ L_{m,j}(Y) = \frac{𝜔_m^j}{m} \frac{Y^m - 1}{Y-𝜔_m^j} $$
Push & Pop
Constraint. (Push). Rotate all elements to the right, add an element $x$. Has the following constraints:
$$ \begin{aligned} P(X, 𝜔_m^{m-1}) &= 0 \\ P(𝜔_n ⋅ X, Y) &= P(X, 𝜔_m ⋅ Y) + x ⋅ L_0(Y) \end{aligned} $$
Constraint. (Pop). Operate the push constraint in reverse.
Random access
Constraint. (Compare and swap). Replace the value at $j$ from $a$ to $b$.
$$ \begin{aligned} P(X, 𝜔_m^j) &= a \\ P(𝜔_n ⋅ X, Y) &= P(X, Y) + (b - a) ⋅ L_j(Y) \end{aligned} $$
The problem here is that we need to encode the $j$ somehow, either in a precomputed polynomial or as a column. Since all usage of $j$ will be in the form $𝜔_m^j$ we will use that instead. the final constraint will look like:
$$ \begin{aligned} P(X, Q(X)) &= a \\ P(𝜔_n ⋅ X, Y) &= P(X, Y) + (b - a) ⋅ \frac{Q(X)}{m} \frac{Y^m - 1}{Y-Q(X)} \end{aligned} $$
To do. What if $Q(X)$ is not of the form $𝜔_m^j$?
The first constraint has a degree bound of $(\deg P)⋅(\deg Q) = n^2 m$. So far we have only handle constant constraint bounds. How do we LDE test this efficiently?
We could add a temporary value? $t = Q(X), P(X, t) = a$?
In addition, to force $Q(X)$ to be a root of unity, we can add a constraint
$$ Q(X)^m = 1 $$
which has degree bound $m\deg Q = nm$. Again, how do we LDE-test this efficiently?
Polynomial composition
Both approaches above hit the problem that we need to low-degree-test an expression of the form $P(Q(X))$. The straightforward approach has degree bound $(\deg P)(\deg Q)$ which is quadratic. This will kill prover performance and more than double proof size.
Goal. Find a way to LDE test polynomial compositions efficiently.
To do. Specify goal more concretely.
https://en.wikipedia.org/wiki/Polynomial_decomposition
https://www.math.mcgill.ca/rickards/PDFs/amer.math.monthly.118.04.358-rickards.pdf
https://www.cs.cornell.edu/~kozen/Papers/poly.pdf
Chebyshev polynomials have the nesting property $T_n(T_m(X)) = T_{mn}(X)$.
https://dspace.mit.edu/bitstream/handle/1721.1/71792/Kedlaya-2011-FAST%20POLYNOMIAL%20FACT.pdf?sequence=1&isAllowed=y https://www.cse.iitk.ac.in/users/nitin/courses/CS681-2016-17-II/pdfs/slides-dwivedi.pdf Evaluates $f(g(x)) \mod h(x)$ in less then $\mathcal O(n^2)$ time using FFTs. => Read. http://users.cms.caltech.edu/~umans/papers/U07.pdf
https://www.cse.iitk.ac.in/users/nitin/courses/CS681-2016-17-II/pdfs/slides-dwivedi.pdf
https://citeseer.ist.psu.edu/viewdoc/download;jsessionid=611B98690C1028968AED2736F9E1E77C?doi=10.1.1.51.3154&rep=rep1&type=pdf
https://arxiv.org/pdf/0807.3578.pdf
Aside: https://en.wikipedia.org/wiki/Bruun's_FFT_algorithm